#include <bits/stdc++.h>

using namespace std;

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
// 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
// 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
// 比如如下两棵树
//         __2
//        /
//       1
//       和
//       1__
//          \
//           2
// 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
// 提交这个类
class Codec 
{
public:
    void f(TreeNode* root, string& ans)
    {
        if(root == nullptr)
        {
            ans += "#,";
        }
        else
        {
            ans += to_string(root->val) + ",";
            f(root->left, ans);
            f(root->right, ans);
        }
    }

    string serialize(TreeNode* root) 
    {
        string ans;
        f(root, ans);
        return ans;
    }

    int cnt;
    
    TreeNode* g(vector<string>& vals)
    {
        string& cur = vals[cnt++];
        if(cur == "#") return nullptr;

        TreeNode* root = new TreeNode(stoi(cur));
        root->left = g(vals);
        root->right = g(vals);
        return root;
    }

    TreeNode* deserialize(string data) 
    {
        vector<string> vals;
        string str;
        cnt = 0;
        // 将序列化后的字符串解析成一个个节点的值
        for(char ch : data)
        {
            if(ch == ',') // 找到了一个节点
            {
                vals.emplace_back(str);
                str.clear(); // 清除之前的数据，重新找下一个节点
            }
            else str += ch;
        }
        return g(vals);
    }
};